5、接龙序列
题目 接龙序列
思路分析
这种朴素做法可以过一半数据 拿到7分
考试时可能优化不出 因为都用dp写了 哪还会去想优化 所以就这样了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int first[N],last[N];
int f[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
string s;cin>>s;
first[i]=s[0]-'0';
last[i]=s.back()-'0';
}
// for(int i=1;i<=n;i++) cout<<first[i]<<" "<<last[i]<<endl;
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(last[j]==first[i]){
f[i]=max(f[i],f[j]+1);
}
}
res=max(res,f[i]);
}
cout<<n-res;
return 0;
}
用g[10];存储第i个数字之前以末尾数字k(0 <= k <= 9)为结尾的接龙序列的max 即g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度
那么就可以省去一层循环
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int first[N],last[N];
int g[N];//g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
string x;
cin>>x;
first[i]=x[0]-'0';
last[i]=x.back()-'0';
}
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
f[i]=max(f[i],g[first[i]]+1);//只关心以first[i]为结尾的数字
g[last[i]]=max(g[last[i]],f[i]);//第i个数字的末尾为last[i],更新g[]
res=max(res,f[i]);
}
cout<<n-res;
return 0;
}
💬 评论